package com.frx.datastruct.chaptereight;

import com.frx.datastruct.chaptertwo.Array;

import java.util.Arrays;

/**
 * Created by xurenfeng on 2019/3/6.
 */
public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    public MaxHeap(){
        data = new Array<>();
    }
    /** 将任意一个数组转换成最大堆*/

    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        // 先找到最后一个非叶子节点
        int startIndex = parent(arr.length-1);
        // 然后从此节点开始，循环进行下沉操作
        for (int i = startIndex; i >= 0; i--){
            siftDown(i);
        }

    }

    public int getSize(){
        return data.getSize();
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }
    /** 元素为index的父亲节点的索引*/
    private int parent(int index){
        if (index == 0){
            throw new IllegalArgumentException("index-0 doesn't has parent !");
        }

        return (index - 1) / 2;
    }

    /** index元素左子节点的索引*/
    private int leftChild(int index){

        return 2 * index + 1;

    }
    /** index元素右子节点的索引*/
    private int rightChild(int index){
        return 2 * index + 2;
    }

    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }
    /** 堆的上浮操作 */
    private void siftUp(int index){

        while (index > 0 && data.get(parent(index)).compareTo(data.get(index)) < 0){

                data.swap(parent(index),index);

            index = parent(index);
        }
    }

    public E findMax(){
        if (data.getSize() == 0){
            throw new IllegalArgumentException("Can't find max when heap is Empty !");
        }
        return data.get(0);
    }


    /** 从堆中取出元素，只能取出堆中最大的元素 */
    public E extractMax(){
        E ret = findMax();

        data.swap(0,data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return ret;
    }
    /** 进行下沉操作 */
    public void siftDown(int k){

        while (leftChild(k) < data.getSize()){
            int j = leftChild(k);
            // 存在右子节点且右子节点大于左子节点
            if ( j+1 < data.getSize() && data.get(j+1).compareTo(data.get(j)) > 0){
                j ++;
            }
            // 如果当前父节点大于子节点，直接退出循环
            if (data.get(k).compareTo(data.get(j)) >= 0){
                break;
            }
            data.swap(k,j);
            k = j;
        }
    }
    /** replace方法 取出堆中最大的元素，然后放入一个新的元素*/
    public E replace(E e){
        // 将栈顶元素进行替换之后执行一次siftDown操作
        E ret = findMax();
        data.set(0,e);
        siftDown(0);
        return ret;
    }

    public static void main(String[] args){
        Integer[] arr = {1,3,4,5,6,9,7};
        System.out.println(Arrays.toString(arr));
        MaxHeap<Integer> maxHeap = new MaxHeap<>(arr);
        System.out.println(maxHeap.data);
        maxHeap.add(8);
        System.out.println(maxHeap.data);
    }

}
